package Solutions

import "container/heap"

type pair struct {
	i int
	j int
	v float64
}

type Pq []*pair

func (p *Pq) Len() int {
	return len(*p)
}
func (p *Pq) Less(i, j int) bool {
	return (*p)[i].v < (*p)[j].v
}

func (p *Pq) Swap(i, j int) {
	(*p)[i], (*p)[j] = (*p)[j], (*p)[i]
}

func (p *Pq) Push(val interface{}) {
	(*p) = append((*p), val.(*pair))
}
func (p *Pq) Pop() interface{} {
	var item = (*p)[len(*p)-1]
	(*p) = (*p)[:len(*p)-1]
	return item
}
func kthSmallestPrimeFraction(arr []int, k int) []int {
	var newPair = func(i, j int) *pair {
		return &pair{
			i: i,
			j: j,
			v: float64(arr[i]) / float64(arr[j]),
		}
	}
	var pq Pq = make([]*pair, 0, len(arr))
	for i := 1; i < len(arr); i++ {
		heap.Push(&pq, newPair(0, i))
	}

	for i := 0; i < k-1; i++ {
		var t = heap.Pop(&pq).(*pair)

		t.i++
		if t.i < t.j {
			t.v = float64(arr[t.i]) / float64(arr[t.j])
			heap.Push(&pq, t)
		}

	}

	var t = heap.Pop(&pq).(*pair)
	var ans = [2]int{arr[t.i], arr[t.j]}
	return ans[:]

}
